/*****************************************************************************
 *  ENTROPY - emerging network to reduce orwellian potency yield
 *
 *  Copyright (C) 2002 Juergen Buchmueller <pullmoll@stop1984.com>
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software Foundation,
 *  Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
 *
 *	$Id: store_mono.c,v 1.4 2005/07/12 23:12:29 pullmoll Exp $
 *****************************************************************************/
#include "osd.h"
#include "config.h"
#include "store.h"
#include "file.h"
#include "logger.h"

#define	INDEXSIZE	(SHA1SIZE + sizeof(time_t))

/* fraction of a store file's keys to search (65536/256 = 256 for 1GB store) */
#define	SEARCH_FRACT	256

/* minimum number of a store file's keys to search */
#define	SEARCH_MIN		16

/* Set this to 1 to initialize a data store with random data */
#define	STORE_INIT_RANDOM	0

/*****************************************************************************
 *	STRATEGY
 *
 *	Data store is kept in one or more (power of two) files, up to 1GB each.
 *	Each store file has up to 64K slots for keys (64K * 16K = 1G)
 *	The offset where a key is kept in the store is derived from the most
 *	significant bytes of its SHA1 value (idx). Up to 16 bits (=64K) define
 *	the position in the store and up to 8 bits (=256) define the store
 *	file number, so a maxmimum of 24 bits of the SHA1 is used, if anyone
 *	should decide to set up a 256GB store.
 *
 *	A separate key index area is kept in each store file. It contains
 *	the full SHA1 value (20 bytes) and a last access time (4 bytes) per key.
 *	Again, the offset where a key is kept within one of the index areas is
 *	derived from the SHA1 MSBs.
 *	In the case of a collision (same idx, different SHA1) the key overwrites
 *	the data in the store. The setting 'storedepth' is used to define a
 *	number of store files; the 'storesize' defines the total size of all
 *	data store files.
 *
 *	The total 'storesize' is rounded to useful values:
 *		8 bits of the idx = 256 slots is the minimum (256 * 16K = 4MB store)
 *		Only 2s exponents are possible for the number of keys per store file,
 *		so with 9 bits you'd have 8MB files, 10 bits = 16MB, 11 bits = 32MB
 *		... up to 16 bits = 1GB files.
 *		The total size is then a multiple of this size times storedepth.
 *	Examples:
 *	storesize=1GB, storedepth=8 results in 8 files with 128MB each
 *	storesize=128MB, storedepth=4 results in 4 files with 32MB each
 *****************************************************************************/

static int store_close(int fd)
{
	FUN("store_close");

	if (-1 == fd) {
		LOGS(L_STORE,L_DEBUG,("fd is -1\n"));
		return 0;
	}
	close(fd);
	return 0;
}

#if	HUGE_MMAP

static int store_open_map(char *file, size_t fno, uint8_t **pmap)
{
	int fd = -1;
	caddr_t map = MAP_FAILED;
	FUN("store_open_map");

	pm_snprintf(file, MAXPATHLEN, "%s/store.%02x",
		g_conf->storepath, fno);

	fd = open(file, O_RDWR|O_BINARY);
	if (-1 == fd) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! open(%s,...) failed (%s)\n",
			file, errmsg));
	}

	if (-1 != fd) {
		map = mmap(NULL, g_conf->storehead,
			PROT_READ | PROT_WRITE, MAP_FILE | MAP_SHARED, fd, 0);
		if (MAP_FAILED == map) {
			const char *errmsg = strerror(errno);
			LOGS(L_STORE,L_ERROR,("FATAL! mmap(%s,%#x,...) failed (%s)\n",
				file, g_conf->storehead, errmsg));
			store_close(fd);
			return -1;
		}
	}

	*pmap = (uint8_t *)map;
	return fd;
}

#else	/* !HUGE_MMAP */

static int store_open(char file[MAXPATHLEN], size_t fno, off_t offs)
{
	int fd;
	FUN("store_open");

	pm_snprintf(file, MAXPATHLEN, "%s/store.%02x",
		g_conf->storepath, fno);
	fd = open(file, O_RDWR|O_BINARY);
	if (-1 == fd) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! open(%s,...) failed (%s)\n",
			file, errmsg));
		return -1;
	}
	if (-1 == lseek(fd, offs, SEEK_SET)) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! lseek(%s,%#x) failed (%s)\n",
			file, (unsigned)offs, errmsg));
		store_close(fd);
		return -1;
	}
	return fd;
}

static int store_seek(int fd, off_t offs)
{
	FUN("store_seek");
	if (-1 == lseek(fd, offs, SEEK_SET)) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! lseek(%d,%#x,SEEK_SET) failed (%s)\n",
			fd, (unsigned)offs, errmsg));
		die(1, "lseek(%d,%#x,SEEK_SET) failed (%s)",
			fd, (unsigned)offs, errmsg);
	}
	return 0;
}

static int store_read_data(int fd, void *buff)
{
	FUN("store_read_data");
	if (CHUNKSIZE != read(fd, buff, CHUNKSIZE)) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! read(%d,%#x,%#x) data failed (%s)\n",
			fd, (unsigned)buff, CHUNKSIZE, errmsg));
		die(1, "read(%d,%#x,%#x) data failed (%s)",
			fd, (unsigned)buff, CHUNKSIZE, errmsg);
	}
	return 0;
}

static int store_write_data(int fd, const void *buff)
{
	FUN("store_write_data");
	if (CHUNKSIZE != write(fd, buff, CHUNKSIZE)) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! write(%d,%#x,%#x) data failed (%s)\n",
			fd, (unsigned)buff, CHUNKSIZE, errmsg));
		die(1, "write(%d,%#x,%#x) data failed (%s)",
			fd, (unsigned)buff, CHUNKSIZE, errmsg);
	}
	return 0;
}

static int store_read_sha1(int fd, sha1_digest_t *sha1)
{
	FUN("store_read_sha1");
	if (SHA1SIZE != read(fd, sha1, sizeof(*sha1))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! read(%d,%#x,%#x) key failed (%s)\n",
			fd, (unsigned)sha1, sizeof(*sha1), errmsg));
		die(1,"read(%d,%#x,%#x) key failed (%s)\n",
			fd, (unsigned)sha1, sizeof(*sha1), errmsg);
	}
	return 0;
}

static int store_write_sha1(int fd, const sha1_digest_t *sha1)
{
	FUN("store_write_sha1");
	if (SHA1SIZE != write(fd, sha1, sizeof(*sha1))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! write(%d,%#x,%#x) key failed (%s)\n",
			fd, (unsigned)sha1, sizeof(*sha1), errmsg));
		die(1, "write(%d,%#x,0x%s) key failed (%s)",
			fd, (unsigned)sha1, sizeof(*sha1), errmsg);
	}
	return 0;
}

static int store_read_time(int fd, time_t *t0)
{
	FUN("store_read_time");
	if (sizeof(time_t) != read(fd, t0, sizeof(time_t))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! read(%d,%#x,%#x) time failed (%s)\n",
			fd, (unsigned)t0, sizeof(time_t), errmsg));
		die(1,"read(%s,%#x,%#x) time failed (%s)\n",
			fd, (unsigned)t0, sizeof(time_t), errmsg);
	}
	return 0;
}

static int store_write_time(int fd, const time_t *t0)
{
	FUN("store_write_time");
	if (sizeof(time_t) != write(fd, time, sizeof(time_t))) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! write(%d,%#x,%#x) time failed (%s)\n",
			fd, (unsigned)t0, sizeof(time_t), errmsg));
		die(1, "write(%d,%#x,0x%s) time failed (%s)",
			fd, (unsigned)t0, sizeof(time_t), errmsg);
	}
	return 0;
}

#endif	/* !HUGE_MMAP */

#if	HUGE_MMAP
/*****************************************************************************
 *	store_put()
 *	Stores a buffer 'buff' of size CHUNKSIZE in a location derived from the
 *	most significant sha1 values.
 *****************************************************************************/
int store_put(const sha1_digest_t *s, const void *buff)
{
	char file[MAXPATHLEN];
	sha1_digest_t *psha1;
	size_t i, idx, pos, fno, fpr, search;
	size_t old_pos, old_mismatch, mismatch;
	off_t offs;
	time_t *pt0, now;
	int fd = -1;
	uint8_t *map;
	FUN("store_put");

	/* use SHA1 digest most significant bytes as an index */
	idx = s->digest[0] | ((uint32_t)s->digest[1] << 8);
	/* derive a file offset and number from SHA1 digest */
	fno = s->digest[3] % g_conf->storedepth;
	pos = idx % g_conf->storekeys;

	search = g_conf->storekeys / SEARCH_FRACT;
	if (search < SEARCH_MIN)
		search = SEARCH_MIN;

	LOGS(L_STORE,L_DEBUG,("put key %s into file %#x at offs %#x\n",
		sha1_hexstr(s), (unsigned)fno, (unsigned)pos));

	STORE_LOCK();
	/* open file to be mmap()ed */
	fd = store_open_map(file, fno, &map);
	if (-1 == fd || MAP_FAILED == (caddr_t)map) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! store_open_map(%s,%#x) failed (%s)\n",
			file, (unsigned)fno, errmsg));
		STORE_UNLOCK();
		return -1;
	}

	now = time(NULL);
	old_pos = pos;
	old_mismatch = 0;
	for (i = 0; i < search; i++) {

		/* file offset: index for pos */
		offs = pos * INDEXSIZE;
		psha1 = (sha1_digest_t *)&map[offs];

		if (0 == memcmp(psha1, &null, SHA1SIZE)) {
			/* hit an empty slot */
			break;
		} else if (0 == memcmp(psha1, s, SHA1SIZE)) {
			/* hit a slot that contains our key */
			store_sub_key(psha1, CHUNKSIZE);
			old_pos = pos;
			break;
		}
		/* look for the worst matching slot (fingeprint and age) */
		pt0 = (time_t *)&map[offs + SHA1SIZE];
		fpr = g_store->fingerprint[keyroute(psha1)];
		mismatch = 256 * (0xff - fpr) + (uint32_t)(now - *pt0);
		if (mismatch > old_mismatch) {
			/* worst matching key so far */
			old_pos = pos;
			old_mismatch = mismatch;
		}
		pos = (pos + 1) % g_conf->storekeys;
	}

	/* did not find an empty or matching slot? */
	if (i >= search) {
		offs = old_pos * INDEXSIZE;
		psha1 = (sha1_digest_t *)&map[offs];
		store_sub_key(psha1, CHUNKSIZE);
		/* overwrite the oldest slot */
		pos = old_pos;
		g_store->seeks[SEEK_SLOTS] += 1;
	} else {
		/* keep track of the number of times we had to seek for the key */
		g_store->seeks[log2size(i)] += 1;
	}

	offs = pos * INDEXSIZE;
	psha1 = (sha1_digest_t *)&map[offs];
	pt0 = (time_t *)&map[offs + SHA1SIZE];
	/* copy hash */
	*psha1 = *s;
	/* set access time */
	*pt0 = time(NULL);

	/* file offset: data for pos */
	offs = g_conf->storehead + pos * CHUNKSIZE;
	if (offs != lseek(fd, offs, SEEK_SET)) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! lseek(%d,%#x,%d) failed (%s)\n",
			fd, (unsigned)offs, SEEK_SET, errmsg));
		munmap(map, g_conf->storehead);
		store_close(fd);
		STORE_UNLOCK();
		return -1;
	}
	if (CHUNKSIZE != write(fd, buff, CHUNKSIZE)) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! write(%d,%p,%#x) failed (%s)\n",
			fd, buff, CHUNKSIZE, errmsg));
		munmap(map, g_conf->storehead);
		store_close(fd);
		STORE_UNLOCK();
		return -1;
	}
	munmap(map, g_conf->storehead);
	store_close(fd);

	store_add_key(s, CHUNKSIZE);

	STORE_UNLOCK();

	return 0;
}

#else
/*****************************************************************************
 *	store_put()
 *	Stores a buffer 'buff' of size CHUNKSIZE in a location derived from the
 *	most significant sha1 values.
 *****************************************************************************/
int store_put(const sha1_digest_t *s, const void *buff)
{
	char file[MAXPATHLEN];
	sha1_digest_t sha1;
	size_t i, idx, pos, fno, fpr, search;
	size_t old_pos, old_mismatch, mismatch;
	off_t offs;
	time_t t0, now;
	int fd = -1;
	FUN("store_put");

	/* use SHA1 digest most significant bytes as an index */
	idx = s->digest[0] | ((uint32_t)s->digest[1] << 8);
	/* derive a file offset and number from SHA1 digest */
	fno = s->digest[3] % g_conf->storedepth;
	pos = idx % g_conf->storekeys;

	search = g_conf->storekeys / SEARCH_FRACT;
	if (search < SEARCH_MIN)
		search = SEARCH_MIN;

	LOGS(L_STORE,L_DEBUG,("put key %s into file %#02x at offs %#x\n",
		sha1_hexstr(s), fno, pos));

	/* file offset: index for pos */
	offs = pos * INDEXSIZE;

	STORE_LOCK();
	/* open and seek to offs */
	fd = store_open(file, fno, offs);

	now = time(NULL);
	old_pos = pos;
	old_mismatch = 0;
	for (i = 0; i < search; i++) {
		store_read_sha1(fd, &sha1);
		if (0 == memcmp(&sha1, &null, SHA1SIZE)) {
			/* hit an empty slot */
			break;
		} else if (0 == memcmp(&sha1, s, SHA1SIZE)) {
			/* hit a slot that contains our key */
			store_sub_key(&sha1, CHUNKSIZE);
			old_pos = pos;
			break;
		}

		/* look for the oldest slot */
		store_read_time(fd, &t0);
		fpr = g_store->fingerprint[keyroute(&sha1)];
		mismatch = 256 * (0xff - fpr) + (uint32_t)(now - *pt0);
		if (mismatch > old_mismatch) {
			/* worst matching key so far */
			old_pos = pos;
			old_mismatch = mismatch;
		}

		pos = (pos + 1) % g_conf->storekeys;
		/* file offset: index for pos */
		offs = pos * INDEXSIZE;
		store_seek(fd, offs);
	}

	/* did not find an empty or matching slot? */
	if (i >= search) {
		offs = old_pos * INDEXSIZE;
		store_read_sha1(fd, &sha1);
		store_sub_key(&sha1, CHUNKSIZE);
		/* overwrite the oldest slot */
		pos = old_pos;
		g_store->seeks[SEEK_SLOTS] += 1;
	} else {
		/* keep track of the number of times we had to seek for the key */
		g_store->seeks[log2size(i)] += 1;
	}

	offs = pos * INDEXSIZE;
	store_seek(fd, offs);
	store_write_sha1(fd, s);
	/* access time */
	t1 = time(NULL);
	store_write_time(fd, &t1);

	/* file offset: data for pos */
	offs = g_conf->storehead + pos * CHUNKSIZE;
	store_seek(fd, offs);
	store_write_data(fd, buff);
	store_close(fd);

	store_add_key(s, CHUNKSIZE);

	STORE_UNLOCK();

	return 0;
}
#endif

#if	HUGE_MMAP
/*****************************************************************************
 *	store_get()
 *	Fetches a buffer 'buff' of size CHUNKSIZE from a store file. The index
 *	and file number are derived from the most significant sha1 values.
 *	Returns -1 if the SHA1 does not exist.
 *****************************************************************************/
int store_get(const sha1_digest_t *s, void *buff)
{
	char file[MAXPATHLEN];
	sha1_digest_t *psha1;
	size_t i, idx, pos, fno, fpr, search;
	off_t offs;
	time_t *pt0;
	int fd = -1;
	uint8_t *map;
	FUN("store_get");

	/* use SHA1 digest most significant bytes as an index */
	idx = s->digest[0] | ((uint32_t)s->digest[1] << 8);

	/* quick check for recently missing keys */
	if (0 == memcmp(&g_store->missing[idx], s, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("missing key #%#04x %s\n",
			(unsigned)idx, sha1_hexstr(s)));
		errno = ENOENT;
		return -1;
	}

	/* if this is an existance check, look up available[] */
	if (NULL == buff &&
		0 == memcmp(&g_store->available[idx], s, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("available key #%#04x %s\n",
			(unsigned)idx, sha1_hexstr(s)));
		return 0;
	}

	/* derive a file offset and number from SHA1 digest */
	fno = s->digest[3] % g_conf->storedepth;
	pos = idx % g_conf->storekeys;

	search = g_conf->storekeys / SEARCH_FRACT;
	if (search < SEARCH_MIN)
		search = SEARCH_MIN;

	/* fingerprint index */
	fpr = keyroute(s);

	LOGS(L_STORE,L_DEBUG,("get key %s from file %#x at offs %#x\n",
		sha1_hexstr(s), (unsigned)fno, (unsigned)pos));

	STORE_LOCK();
	/* open file to be mmap()ed */
	fd = store_open_map(file, fno, &map);
	if (-1 == fd || MAP_FAILED == (caddr_t)map) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! store_open_map(%s,%#x) failed (%s)\n",
			file, (unsigned)fno, errmsg));
		STORE_UNLOCK();
		return -1;
	}

	for (i = 0; i < search; i++) {
		/* file offset: index for pos */
		offs = pos * INDEXSIZE;
		psha1 = (sha1_digest_t *)&map[offs];

		if (0 == memcmp(psha1, s, SHA1SIZE)) {
			/* write access time */
			pt0 = (time_t *)&map[offs + SHA1SIZE];
			*pt0 = time(NULL);
			munmap(map, g_conf->storehead);

			if (NULL != buff) {
				/* file offset: data for pos */
				offs = g_conf->storehead + pos * CHUNKSIZE;
				if (offs != lseek(fd, offs, SEEK_SET)) {
					const char *errmsg = strerror(errno);
					LOGS(L_STORE,L_ERROR,("FATAL! lseek(%d,%#x,%d) failed (%s)\n",
						fd, (unsigned)offs, SEEK_SET, errmsg));
					store_close(fd);
					STORE_UNLOCK();
					return -1;
				}
				if (CHUNKSIZE != read(fd, buff, CHUNKSIZE)) {
					const char *errmsg = strerror(errno);
					LOGS(L_STORE,L_ERROR,("FATAL! read(%d,%p,%#x) failed (%s)\n",
						fd, buff, CHUNKSIZE, errmsg));
					store_close(fd);
					STORE_UNLOCK();
					return -1;
				}
			}
			store_close(fd);
			/* keep track of the number of times we had to seek for the key */
			g_store->seeks[log2size(i)] += 1;
			/* reset missing[] entry for this index */
			g_store->missing[idx] = null;
			/* set available[] entry for this index */
			g_store->available[idx] = *s;
			STORE_UNLOCK();
			return 0;
		}
		pos = (pos + 1) % g_conf->storekeys;
	}
	munmap(map, g_conf->storehead);
	store_close(fd);

	g_store->seeks[log2size(i)] += 1;
	/* set missing[] entry for this index */
	g_store->missing[idx] = *s;
	/* reset available[] entry for this index */
	g_store->available[idx] = null;
	STORE_UNLOCK();

	errno = ENOENT;
	return -1;
}

#else
/*****************************************************************************
 *	store_get()
 *	Fetches a buffer 'buff' of size CHUNKSIZE from a store file. The index
 *	and file number are derived from the most significant sha1 values.
 *	Returns -1 if the SHA1 does not exist.
 *****************************************************************************/
int store_get(const sha1_digest_t *s, void *buff)
{
	char file[MAXPATHLEN];
	sha1_digest_t sha1;
	size_t i, idx, pos, fno, fpr, search;
	off_t offs;
	time_t t0;
	int fd = -1;
	FUN("store_get");

	/* use SHA1 digest most significant bytes as an index */
	idx = s->digest[0] | ((uint32_t)s->digest[1] << 8);

	/* quick check for recently missing keys */
	if (0 == memcmp(&g_store->missing[idx], s, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("missing key #%#04x %s\n",
			(unsigned)idx, sha1_hexstr(s)));
		errno = ENOENT;
		return -1;
	}

	/* if this is an existance check, look up available[] */
	if (NULL == buff &&
		0 == memcmp(&g_store->available[idx], s, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("available key #%#04x %s\n",
			(unsigned)idx, sha1_hexstr(s)));
		return 0;
	}

	/* derive a file offset and number from SHA1 digest */
	fno = s->digest[3] % g_conf->storedepth;
	pos = idx % g_conf->storekeys;

	search = g_conf->storekeys / SEARCH_FRACT;
	if (search < SEARCH_MIN)
		search = SEARCH_MIN;

	/* fingerprint index */
	fpr = keyroute(s);

	LOGS(L_STORE,L_DEBUG,("get key %s from file %#02x at offs %#x\n",
		sha1_hexstr(s), (unsigned)fno, (unsigned)pos));

	/* file offset: index for pos */
	offs = pos * INDEXSIZE;

	STORE_LOCK();
	/* open and seek to offs */
	fd = store_open(file, fno, offs);

	for (i = 0; i < search; i++) {
		store_read_sha1(fd, &sha1);

		/* check if this key matches */
		if (0 == memcmp(&sha1, s, SHA1SIZE)) {
			/* write access time */
			t0 = time(NULL);
			store_write_time(fd, &t0);
			if (NULL != buff) {
				/* file offset: data for pos */
				offs = g_conf->storehead + pos * CHUNKSIZE;
				store_seek(fd, offs);
				store_read_data(fd, buff);
			}
			store_close(fd);
			/* keep track of the number of times we had to seek for the key */
			g_store->seeks[log2size(i)] += 1;
			/* reset missing[] entry for this index */
			g_store->missing[idx] = null;
			/* set available[] entry for this index */
			g_store->available[idx] = *s;
			STORE_UNLOCK();
			return 0;
		}
		pos = (pos + 1) % g_conf->storekeys;
		/* file offset: index for pos */
		offs = pos * INDEXSIZE;
		store_seek(fd, offs);
	}
	store_close(fd);

	g_store->seeks[log2size(i)] += 1;
	/* set missing[] entry for this index */
	g_store->missing[idx] = *s;
	/* reset available[] entry for this index */
	g_store->available[idx] = null;
	STORE_UNLOCK();

	errno = ENOENT;
	return -1;
}
#endif

#if	HUGE_MMAP
/*****************************************************************************
 *	store_commit()
 *	Delete the file with a name that is derived from the sha1 values.
 *	The path is built from the storepath and a up to two-level
 *	sub-directory consisting of nibbles of sha1.
 *****************************************************************************/
static int store_commit(const sha1_digest_t *s, size_t size)
{
	char file[MAXPATHLEN];
	sha1_digest_t *psha1;
	size_t i, idx, pos, fno, fpr, search;
	off_t offs;
	time_t *pt0;
	int fd = -1;
	uint8_t *map;
	FUN("store_commit");

	/* use SHA1 digest most significant bytes as an index */
	idx = s->digest[0] | ((uint32_t)s->digest[1] << 8);

	/* quick check for recently missing keys */
	if (0 == memcmp(&g_store->missing[idx], s, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("missing key #%#04x %s\n",
			(unsigned)idx, sha1_hexstr(s)));
		errno = ENOENT;
		return -1;
	}

	/* derive a file offset and number from SHA1 digest */
	fno = s->digest[3] % g_conf->storedepth;
	pos = idx % g_conf->storekeys;

	search = g_conf->storekeys / SEARCH_FRACT;
	if (search < SEARCH_MIN)
		search = SEARCH_MIN;

	/* fingerprint index */
	fpr = keyroute(s);

	/* open file to be mmap()ed */
	fd = store_open_map(file, fno, &map);
	if (-1 == fd || MAP_FAILED == (caddr_t)map) {
		const char *errmsg = strerror(errno);
		LOGS(L_STORE,L_ERROR,("FATAL! store_open_map(%s,%#x) failed (%s)\n",
			file, (unsigned)fno, errmsg));
		return -1;
	}

	for (i = 0; i < search; i++) {
		/* file offset: index for pos */
		offs = pos * INDEXSIZE;
		psha1 = (sha1_digest_t *)&map[offs];

		/* check if this key really matches */
		if (0 == memcmp(psha1, s, SHA1SIZE)) {
			store_sub_key(psha1, size);

			/* keep track of the number of times we had to seek for the key */
			g_store->seeks[log2size(i)] += 1;

			pt0 = (time_t *)&map[offs + SHA1SIZE];
			*psha1 = null;
			*pt0 = (time_t)0;
			munmap((caddr_t)map, g_conf->storehead);
			store_close(fd);
			LOGS(L_STORE,L_DEBUG,("key %s deleted\n",
				sha1_hexstr(s)));
			return 0;
		}
		pos = (pos + 1) % g_conf->storekeys;
	}
	munmap((caddr_t)map, g_conf->storehead);

	store_close(fd);
	errno = ENOENT;
	return -1;
}
#else
/*****************************************************************************
 *	store_commit()
 *	Delete the file with a name that is derived from the sha1 values.
 *	The path is built from the storepath and a up to two-level
 *	sub-directory consisting of nibbles of sha1.
 *****************************************************************************/
static int store_commit(const sha1_digest_t *s, size_t size)
{
	char file[MAXPATHLEN];
	sha1_digest_t sha1;
	size_t i, idx, pos, fno, fpr, search;
	off_t offs;
	time_t t0;
	int fd = -1;
	FUN("store_commit");

	/* use SHA1 digest most significant bytes as an index */
	idx = s->digest[0] | ((uint32_t)s->digest[1] << 8);

	/* quick check for recently missing keys */
	if (0 == memcmp(&g_store->missing[idx], s, SHA1SIZE)) {
		LOGS(L_STORE,L_DEBUGX,("missing key #%#04x %s\n",
			(unsigned)idx, sha1_hexstr(s)));
		errno = ENOENT;
		return -1;
	}

	/* derive a file offset and number from SHA1 digest */
	fno = s->digest[3] % g_conf->storedepth;
	pos = idx % g_conf->storekeys;

	search = g_conf->storekeys / SEARCH_FRACT;
	if (search < SEARCH_MIN)
		search = SEARCH_MIN;

	/* fingerprint index */
	fpr = keyroute(s);

	/* file offset: index for pos */
	offs = pos * INDEXSIZE;

	/* open and seek to offs */
	fd = store_open(file, fno, offs);

	for (i = 0; i < search; i++) {
		store_read_sha1(fd, &sha1);
		/* check if this key really matches */
		if (0 == memcmp(&sha1, s, SHA1SIZE)) {
			store_sub_key(&sha1, CHUNKSIZE);

			/* keep track of the number of times we had to seek for the key */
			g_store->seeks[log2size(i)] += 1;

			store_seek(fd, offs);
			store_write_sha1(fd, &null);
			t0 = (time_t)0;
			store_write_time(fd, &t0);
			store_close(fd);
			LOGS(L_STORE,L_DEBUG,("key %s deleted\n",
				sha1_hexstr(s)));
			return 0;
		}
		pos = (pos + 1) % g_conf->storekeys;
		/* file offset: index for pos */
		offs = pos * INDEXSIZE;
	}

	store_close(fd);
	errno = ENOENT;
	return -1;
}
#endif

/*
 *	store_purge()
 *	Dummy in this implementation.
 */
int store_purge(void)
{
#if	HUGE_MMAP
	char file[MAXPATHLEN];
	uint8_t *map;
	size_t fno;
	int fd;
	FUN("store_purge");

	for (fno = 0; fno < g_conf->storedepth; fno++) {
		/* open file to be mmap()ed */
		fd = store_open_map(file, fno, &map);
		if (-1 == fd) {
			const char *errmsg = strerror(errno);
			LOGS(L_STORE,L_ERROR,("FATAL! store_open_map(%s,%#x) failed (%s)\n",
				file, (unsigned)fno, errmsg));
			continue;
		}

		if (-1 == msync(map, g_conf->storehead, MS_ASYNC)) {
			const char *errmsg = strerror(errno);
			LOGS(L_STORE,L_ERROR,("FATAL! msync(%s,...) failed (%s)\n",
				file, errmsg));
		}
		munmap(map, g_conf->storehead);
		store_close(fd);
		LOGS(L_STORE,L_MINOR,("synchronized store file #%02x\n",
			(unsigned)fno));
	}
#else
	FUN("store_purge");
#endif

	return 0;
}

/*****************************************************************************
 *	store_del()
 *	Enter a key into the list of pending deletes (drop key list).
 *	If the list is full, delete the earliest key now, sort the list by
 *	time (in case we would use varying timeouts) and make room for one
 *	new entry. Afterwards, commit all pending deletes that expired.
 *****************************************************************************/
int store_del(const sha1_digest_t *psha1)
{
	size_t i, j;
	drop_key_t *d;
	time_t t0;
	int rc = 0;
	FUN("store_del");

	if (NULL == psha1) {
		LOGS(L_STORE,L_ERROR,("psha1 is NULL\n"));
		errno = EINVAL;
		return -1;
	}

	STORE_LOCK();
	/* first check if this delete is already pending */
	for (i = g_store->tail; i != g_store->head; i = (i + 1) % DROP_MAX) {
		d = &g_store->drop[i];
		if (0 == memcmp(&d->sha1, psha1, SHA1SIZE)) {
			STORE_UNLOCK();
			return 0;
		}
	}

	/* if we cannot simply add another drop key entry */
	if ((g_store->head + 1) % DROP_MAX == g_store->tail) {
		LOGS(L_STORE,L_MINOR,("list is full: committing %d pending deletes\n",
			DROP_MAX/8));
#if	STORE_QSORT
		/* sort by drop time -- earliest first */
		qsort(g_store->drop, DROP_MAX, sizeof(drop_key_t),
			store_sort_drop_time);
		g_store->tail = 0;
		g_store->head = DROP_MAX - 1;
#endif
		/* now drop the earliest DROP_MAX/8 keys */
		for (i = g_store->tail, j = 0; j < DROP_MAX/8; j++) {
			d = &g_store->drop[i];
			LOGS(L_STORE,L_DEBUG,("committing key %s delete due %s\n",
				sha1_hexstr(&d->sha1),
				datetime_str(d->time)));
			if (0 != (rc = store_commit(&d->sha1, d->size))) {
				LOGS(L_STORE,L_DEBUG,("committing failed (%s)\n",
					strerror(errno)));
			}
			i = (i + 1) % DROP_MAX;
		}

		/* new tail after committing 'j' deletes */
		g_store->tail = i;

		LOGS(L_STORE,L_MINOR,("removed %d entries; list has %d entries now\n",
			(int)j,
			(int)(g_store->head >= g_store->tail ?
				g_store->head - g_store->tail :
				g_store->head + DROP_MAX - g_store->tail)));
	}

	t0 = time(NULL);

	/* enter this key in the head slot */
	d = &g_store->drop[g_store->head];
	g_store->head = (g_store->head + 1) % DROP_MAX;
	d->sha1 = *psha1;
	d->time = t0 + 180;	/* nuke in 180 seconds = 3 minutes from now */
	d->size = CHUNKSIZE;
	LOGS(L_STORE,L_DEBUG,("appended key drop %s (%d bytes) at %s\n",
		sha1_hexstr(&d->sha1),
		(int)d->size, datetime_str(d->time)));

	/* now commit keys which expired their timeout */
	for (i = g_store->tail, j = 0; i != g_store->head; j++) {
		d = &g_store->drop[i];
		if (d->time > t0) {
			break;
		}
		LOGS(L_STORE,L_DEBUG,("committing key %s delete due %s\n",
			sha1_hexstr(&d->sha1),
			datetime_str(d->time)));
		if (0 != (rc = store_commit(&d->sha1, d->size))) {
			LOGS(L_STORE,L_DEBUG,("committing failed (%s)\n",
				strerror(errno)));
		}
		i = (i + 1) % DROP_MAX;
	}

	/* committed some keys? */
	if (j > 0) {
		g_store->tail = i;
		LOGS(L_STORE,L_MINOR,("removed %d entries; list has %d entries now\n",
			(int)j,
			(int)(g_store->head >= g_store->tail ?
				g_store->head - g_store->tail :
				g_store->head + DROP_MAX - g_store->tail)));
	}
	
	STORE_UNLOCK();
	return 0;
}

/*****************************************************************************
 *	store_zap()
 *	Immediately zap a key from the store.
 *****************************************************************************/
int store_zap(const sha1_digest_t *psha1)
{
	int rc = 0;
	FUN("store_zap");

	if (NULL == psha1) {
		LOGS(L_STORE,L_ERROR,("psha1 is NULL\n"));
		errno = EINVAL;
		return -1;
	}

	STORE_LOCK();
	rc = store_commit(psha1, CHUNKSIZE);
	STORE_UNLOCK();

	return rc;
}

/*****************************************************************************
 *	store_check()
 *	Check if 'required' of 'count' keys specified in '*sha1' that are marked
 *	(non-zero bit) in flags are available in the store.
 *****************************************************************************/
int store_check(const sha1_digest_t *sha1, int flags, size_t count, size_t required)
{
	size_t i, have = 0;
	FUN("store_check");

	for (i = 0; i < count; i++) {
		if (0 == (flags & (1 << i))) {
			have++;
		} else if (0 == store_get(&sha1[i], NULL)) {
			have++;
		}
	}
	if (have < required) {
		/* at least one is missing */
		errno = ENOENT;
		return -1;
	}
	return 0;
}

void store_exit(int sig)
{
	FUN("store_exit");

	signal(sig, SIG_DFL);
	LOGS(L_STORE,L_MINOR,("*** {%d} signal %s ***\n",
		(int)getpid(), signal_name(sig)));
	osd_exit(sig);
}

int store(void)
{
	char file[MAXPATHLEN];
	sha1_digest_t sha1;
	size_t size, pos, fno, fpr;
	time_t t0;
	uint8_t *fill;
	int zap, fd = -1, rc = 0;
	FUN("store");

	if (g_conf->storesize < 4 * 1024 * 1024) {
		info("%u bytes is not enough (4MB is minimum)!", g_conf->storesize);
		errno = EINVAL;
		return -1;
	}

	/* find number of keys per store file (no more than 1GB per store) */
	g_conf->storekeys = g_conf->storesize / CHUNKSIZE / g_conf->storedepth;
	while ((uint64_t)g_conf->storekeys * CHUNKSIZE > (uint64_t)1024 * 1024 * 1024) {
		g_conf->storekeys >>= 1;
		g_conf->storedepth <<= 1;
	}

	/* min and max for storedepth (aka number of store files) */
	if (g_conf->storedepth < 1) {
		g_conf->storedepth = 1;
	} else if (g_conf->storedepth > 256) {
		g_conf->storedepth = 256;
	}

	/* size of the header of each store file */
	g_conf->storehead = g_conf->storekeys * INDEXSIZE;

	info("%u*%u keys; ", g_conf->storedepth, g_conf->storekeys);

	/* capture signals */
	set_signal_handler(SIGHUP, store_exit);
	set_signal_handler(SIGINT, store_exit);
	set_signal_handler(SIGPIPE, store_exit);
	set_signal_handler(SIGALRM, store_exit);
	set_signal_handler(SIGTERM, store_exit);

	size = sizeof(store_t);
	g_store = (store_t *)scalloc(size, 1);
	if (NULL == g_store) {
		LOGS(L_STORE,L_ERROR,("failed to mmap() store; size %d (%s)\n",
			(int)size, strerror(errno)));
		return -1;
	}

	if (0 != (rc = osd_sem_init(&g_store->sem, 1, 1))) {
		LOGS(L_STORE,L_ERROR,("osd_sem_init(%p,%d,%d) call failed (%s)\n",
			&g_store->sem, 1, 1, strerror(errno)));
		return -1;
	}

	g_store->storesize = g_conf->storesize;

	pm_snprintf(file, MAXPATHLEN, "%s", g_conf->storepath);
	if (0 != mkdir(file, 0700)) {
		if (EEXIST != errno)
			LOGS(L_STORE,L_ERROR,("mkdir('%s') failed (%s)\n",
				file, strerror(errno)));
	}

	zap = store_get_version();

	/* one week back */
	t0 = time(NULL) - 7 * 24 * 60 * 60;

	info("  0%%\b\b\b\b");
	for (fno = 0; fno < g_conf->storedepth; fno++) {
		pm_snprintf(file, MAXPATHLEN, "%s/store.%02x",
			g_conf->storepath, fno);
		fd = (0 == zap) ? open(file, O_RDWR|O_BINARY) : -1;
		if (-1 == fd) {
			fill = xcalloc(CHUNKSIZE, sizeof(char));
			fd = open(file, O_RDWR|O_CREAT|O_TRUNC|O_BINARY, 0644);
			if (-1 == fd) {
				const char *errmsg = strerror(errno);
				LOGS(L_STORE,L_ERROR,("FATAL! open(%s,...) failed (%s)\n",
					file, errmsg));
				die(1, "open(%s,...) failed (%s)", file, errmsg);
			}

			/* fill the SHA1 key index range */
			size = INDEXSIZE;
			for (pos = 0; pos < g_conf->storekeys; pos++) {
#if	STORE_INIT_RANDOM
				if (0 != get_rnd(fill, size)) {
					const char *errmsg = strerror(errno);
					LOGS(L_STORE,L_ERROR,("FATAL! get_rnd(...,%x) failed (%s)\n",
						size, errmsg));
					die(1, "get_rnd(...,%x) failed (%s)", size, errmsg);
				}
				*(time_t *)&fill[SHA1SIZE] %= 7 * 24 * 60 * 60;
				*(time_t *)&fill[SHA1SIZE] += t0;
#endif
				if (size != (size_t)write(fd, fill, size)) {
					const char *errmsg = strerror(errno);
					LOGS(L_STORE,L_ERROR,("FATAL! write(%s,...) failed (%s)\n",
						file, errmsg));
					die(1, "write(%s,...) failed (%s)", file, errmsg);
				}
#if	STORE_INIT_RANDOM
				fpr = keyroute((sha1_digest_t *)fill);
				g_store->storecount += 1;
				g_store->currsize += CHUNKSIZE;
				g_store->keycount[fpr] += 1;
#endif
			}

			/* fill the data range with garbage */
			size = CHUNKSIZE;
			for (pos = 0; pos < g_conf->storekeys; pos++) {
#if	STORE_INIT_RANDOM
				if (0 != get_rnd(fill, size)) {
					const char *errmsg = strerror(errno);
					LOGS(L_STORE,L_ERROR,("FATAL! get_rnd(...,%x) failed (%s)\n",
						size, errmsg));
					die(1, "get_rnd(...,%x) failed (%s)", size, errmsg);
				}
#endif
				if (size != (size_t)write(fd, fill, size)) {
					const char *errmsg = strerror(errno);
					LOGS(L_STORE,L_ERROR,("FATAL! write(%s,...) failed (%s)\n",
						file, errmsg));
					die(1, "write(%s,...) failed (%s)", file, errmsg);
				}
				if (0 == (pos % 1024)) {
					int pct = 100 * ((fno * g_conf->storekeys) + pos) /
						g_conf->storedepth / g_conf->storekeys;
					info("%3d%%\b\b\b\b", pct);
					osd_usleep(100000);
				}
			}
			xfree(fill);
			close(fd);
			fd = -1;
		} else {
#if	HUGE_MMAP
			uint8_t *map;

			map = (uint8_t *)mmap(NULL, g_conf->storehead,
				PROT_READ | PROT_WRITE, MAP_FILE | MAP_SHARED, fd, 0);
			if (MAP_FAILED == (caddr_t)map) {
				const char *errmsg = strerror(errno);
				LOGS(L_STORE,L_ERROR,("FATAL! mmap(%s,%#x,...) failed (%s)\n",
					file, g_conf->storehead, errmsg));
				STORE_UNLOCK();
				return -1;
			}
			for (pos = 0; pos < g_conf->storekeys; pos++) {
				size_t offs = pos * INDEXSIZE;
				memcpy(&sha1, &map[offs], SHA1SIZE);
				if (0 != memcmp(&sha1, &null, SHA1SIZE)) {
					fpr = keyroute(&sha1);
					g_store->storecount += 1;
					g_store->currsize += CHUNKSIZE;
					g_store->keycount[fpr] += 1;
				}
				if (0 == (pos % 1024)) {
					int pct = 100 * ((fno * g_conf->storekeys) + pos) /
						g_conf->storedepth / g_conf->storekeys;
					info("%3d%%\b\b\b\b", pct);
				}
			}
			munmap((caddr_t)map, g_conf->storehead);
#else
			for (pos = 0; pos < g_conf->storekeys; pos++) {
				store_read_sha1(fd, &sha1);
				if (0 != memcmp(&sha1, &null, SHA1SIZE)) {
					fpr = keyroute(&sha1);
					g_store->storecount += 1;
					g_store->currsize += CHUNKSIZE;
					g_store->keycount[fpr] += 1;
				}
				if (0 == (pos % 1024)) {
					int pct = 100 * ((fno * g_conf->storekeys) + pos) /
						g_conf->storedepth / g_conf->storekeys;
					info("%3d%%\b\b\b\b", pct);
				}
			}
#endif
			close(fd);
			fd = -1;
		}
	}

	/* write the version info */
	if (0 != (rc = store_put_version(zap))) {
		return rc;
	}

	store_upd_fingerprint();
	LOGS(L_STORE,L_NORMAL,("Opened %uMB [%uMB] %d file store with %d keys\n",
		(unsigned)(g_store->currsize / 1024 / 1024),
		(unsigned)(g_store->storesize / 1024 / 1024),
		(int)g_conf->storedepth,
		(int)g_store->storecount));
	info("%uMB [%uMB] %d file, %d keys ",
		(unsigned)(g_store->currsize / 1024 / 1024),
		(unsigned)(g_store->storesize / 1024 / 1024),
		(int)g_conf->storedepth,
		(int)g_store->storecount);

	return rc;
}
